package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/01/31 10:10
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 题目 ：括号生成
 * 题目详述 ：
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 提示：
 * 1 <= n <= 8
 */
public class GenerateParenthesis {
    /**
     * 思路 ：
     * 由于需要获取能够生成所有可能的并且有效的括号组合，即求解所有可能解（回溯法）;
     * ===> 回溯法的核心，在于使用递归方式，来获取所有可能的结果集;
     *
     * 满足条件 ：
     * （1）所使用的左括号数量 >= 所使用的右括号数量;
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        /**
         * flushBack函数 ：
         * （1）左括号个数;
         * （2）右括号个数;
         * （3）字符串s;
         * （4）结果集合;
         */
        flushBack(n,n,"",result);
        return result;
    }

    private void flushBack(int m, int n, String str, List<String> result) {
        // 递归结束条件 ：即，左右括号皆使用完毕;
        if(m == 0 && n == 0){
            result.add(str);
        }
        // 需要满足的隐性条件 ：所使用的左括号数量 >= 所使用的右括号数量
        if(m <= n){
            // 当左括号未被使用完时,优先使用左括号;
            if(m > 0){
                flushBack(m - 1, n , str + "(" , result);
            }
            flushBack(m , n - 1 , str + ")" , result);
        }
    }
}
